import java.util.ArrayList;

/**
 * Created with IntelliJ IDEA.
 * Description: 在一个二维数组array中（每个一维数组的长度相同），
 *              每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。
 *              请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
 * Date: 2022-09-28
 */


class Solution {
    public static boolean Find(int target, ArrayList< ArrayList<Integer> > array) {

        if(array == null) { return false; }

        int i = 0;
        int j = array.get(0).size() - 1;

        while( i < array.size() && j >= 0) {
            if(array.get(i).get(j) < target) {
                i++;
            } else if(array.get(i).get(j) > target) {
                j--;
            } else {
                return true;
            }
        }
        return false;
    }
}

public class Test {
    public static void main(String[] args) {
        ArrayList<ArrayList<Integer>> array = new ArrayList<>();

        ArrayList<Integer> arrayList1 = new ArrayList<>(); // 添加1 2 8 9
        arrayList1.add(1);
        arrayList1.add(2);
        arrayList1.add(8);
        arrayList1.add(9);

        ArrayList<Integer> arrayList2 = new ArrayList<>(); // 添加2 4 9 12
        arrayList2.add(2);
        arrayList2.add(4);
        arrayList2.add(9);
        arrayList2.add(12);

        ArrayList<Integer> arrayList3 = new ArrayList<>(); // 添加4 7 10 13
        arrayList3.add(4);
        arrayList3.add(7);
        arrayList3.add(10);
        arrayList3.add(13);

        ArrayList<Integer> arrayList4 = new ArrayList<>(); // 添加6 8 11 15
        arrayList4.add(6);
        arrayList4.add(8);
        arrayList4.add(11);
        arrayList4.add(15);


        array.add(arrayList1);
        array.add(arrayList2);
        array.add(arrayList3);
        array.add(arrayList4);

        System.out.println(Solution.Find(7,array));
        System.out.println(Solution.Find(3,array));

        //System.out.println(array.get(0).size() - 1);

    }
}
